package leetbook.sort_search;

import java.util.Arrays;

public class Solution324 {

    public static void main(String[] args) {

//        int[] nums = {4,5,5,6};
//        new Solution324().wiggleSort(nums);

        int[] nums = {};
        int[] help=nums.clone();
        System.out.println(help);
        System.out.println(nums);
    }

    public void wiggleSort1(int[] nums) {
        int[] help=nums.clone();
        Arrays.sort(help);
        int N=nums.length;
        for(int i=1;i<nums.length;i+=2){
            nums[i]=help[--N];
        }
        for(int i=0;i<nums.length;i+=2){
            nums[i]=help[--N];
        }
    }

    /**
     * 整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序
     * 思路：排序，后半部往前半部插入
     */
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.sort(nums);
        //i是小的那半部分下标，范围[0,mid]，j是较大半部分的下标，范围(mid,n-1],
        //小半部分长度要么比大半部分长1或等长
        int i=0, mid=(n-1)/2, j=mid+1, k=0;
        //防止交叉重合，把两部分都反序
        for (int l = 0, r = mid; l < r; l++,r--) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
        for (int l = j, r = n-1; l < r; l++,r--) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
        //交叉放入
        while (j<n){
            res[k++] = nums[i++];
            res[k++] = nums[j++];
        }
        //要看n是奇数偶数，n为偶数就结束了，如果n为奇数，小半部还有一个数未添加
        if((n&1)==1) res[k] = nums[i];
        for (int l = 0; l < n; l++) {
            nums[l] = res[l];
        }
    }
}
